Power Programmierung 2

home *** CD-ROM | disk | FTP | other *** search

/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / database / salve / salve.man < prev next >

Wrap

Text File | 1988-06-02 | 152.6 KB | 7,723 lines

Copyright Ron Albury 1988 INTRODUCTION INTRODUCTION SALVE SOFTWARE Several years ago I was watching a sit-com on TV. In it a man had lost his job, and was picking up pocket money selling some kind of salve. It was never really clear what you were supposed to use the salve for. When ever someone would ask him what it was for he would say, "Use it for what ever you want". It was a running joke for the whole episode. In the last scene a slightly goofy secondary character said he was running out of salve and wanted to buy some more. Everyone turned to him and asked what he used it for. The answer, of course, was: "What ever you want". While I am not out of a job, I am desperately in need of some extra money. I decided to develop some utility software functions and distribute them as shareware. These routines are not applications in and of themselves. Their purpose is just to make your application development go a little easier. What can you use Salve Software for? Anything you want! SHAREWARE I developed the Salve Data Management Library to make my life, and the lives of other program developers, a little easier. If you believe this library is a useful tool and you want it supported and improved you should voice your support by registering it with me. If you are planning to use the library frequently or in a revenue generating program, please send a contribution to: Ron Albury Salve Software 660 Brandy Way Cincinnati, OH 45244. In addition to the above address you can reach me on Compuserve [73577,121]. Due to my erratic schedule you have the greatest chance of reaching me if you use EMAIL. Private individuals may register their personal use of the library for a $20.00 contribution. Profit making organizations, or individuals using the library in a revenue generating software program, should contribute $50.00 per development CPU. Salve Data Management Library may be linked into programs which are subsequently released, given or sold, without additional licenses or fees. You may not release, give, or sell linkable objects or libraries containing Salve Data Management routines without prior approval. You may move registered libraries between systems at no additional charge as long as the files are only available on one system at a time. - 1 - Copyright Ron Albury 1988 Source code is available for restricted use: private use/$50.00, revenue generating/$100.00. The source code may not be released, given, sold, used to create unregistered copies of the library, or in any way used to circumvent the previously stated restrictions. Site licences and/or unrestricted licences are negotiable. This software is protected both by United States Copyright Law and international treaty provisions. Using the Salve Data Management Library in a revenue generating program, without first registering, is a definite no-no. This software tool is distributed through public channels and relies on the goodwill of its users for survival. Please feel free to distribute the shareware version of this package to your friends, your enemies, or anyone else you can think of. I only ask that you do so without altering any of the files, and that all files that I have supplied to you are included in any distribution. I specifically disclaim any implied warranties, and in no way shall I be liable for any loss of profit or any other damage, including but not limited to special, incidental, consequential or other damages. If you want me to 'byte' off that kind of liability you'd better be willing to pay a lot more money than I asked for. However, I will attempt to help registered users of the package with any technical problems they may have. I will also attempt to incorporate as many suggestions as possible in future releases. If you find a bug please report it to me. If I agree that it is a bug I will either correct the problem or I will refund your registration money. DESIGN APPROACH In my experience, most of the art of programming is developing and managing data structures. Even Niklaus Wirth supports this contention with his book "Algorithms + Data ____________________ Structures = Programs". I've developed everything from _________________________ business applications to real time factory control software, and in every case the first thing I had to do was to solve the data management problem. I have always liked the software class concept. I am not _____ very familiar with the classic object oriented languages like Smalltalk. However I have had quite a bit of experience with a special superset of Pascal that supported the class concept. The intent of these routines is to treat a number of classic data management structures as if they are just variables capable of holding multiple values. The functions I have supplied constitute the set of operations defined for those variables. - 2 - Copyright Ron Albury 1988 I have not provided any spiffy macros to hide the fact that you are accessing C functions. I have not introduced any new syntax to support the illusion of a software class. If you can _____ not or do not want to relate to these routines in terms of classes, try thinking of them as temporary files with special _______ _________ capabilities. Each instance of a data class (such as a tree or a linked list) that you put into your program is opened up, just like a file. You can open up several different types data structures, or several instances of the same type of data structure. When you open up the structure you are given a 'root' (or 'handle') to that instance. From then on you use that root whenever you access that data class, just as you would with a file. When you are done with the class you close the handle, just as you would with a file. When I was designing the library I had to decide how to store your data in the classes. Each class of data management (tree, list, hash, etc.) requires different data to support its maintenance. One approach would have been to have you include some of this support overhead in your data records (such as front and back pointers with lists, or left and right pointers with trees). I decided against this approach, instead choosing to have you pass a pointer to the 'bare' data record you want stored. It is then up to the management functions to allocate any extra data fields necessary to link your data in. This way your data records do not have to change, no matter what data management technique you use to handle them. Perhaps this is not the most efficient technique in absolute cpu cycles, but it does provide you the most flexibility in what you store and how you store it. One aspect of this added flexibility is the fact that you can store things other than pointers to data structures. The Salve routines know only that you are passing in a 32 bit value. With proper care it is possible, under some circumstances, to forgo the overhead of allocating a data structure and directly store a 32 bit value into the data management class. Be warned, however, that if you store a zero value in this manner, the debug library will report a non-fatal warning There is nothing inherently complicated or difficult about what I am providing here. Any one of you, given a little time (actually it took me more than a little time) and a little motivation, would probably do as good of a job as I did. In fact, most of you probably have developed bits and pieces of this library, over and over and over again. Like the chain - 3 - Copyright Ron Albury 1988 smoker said, "It's easy to give up cigarettes. I must have done it three or four times last year." The challenge was not just to write some data management routines, but to develop the routines in a flexible enough way to avoid doing it three or four times in a year. - 4 - Copyright Ron Albury 1988 USE OF POINTERS IN FUNCTIONS One problem with passing pointers around in generic functions is how to declare the parameters in the function prototypes. The ANSI committee made things easier by allowing void pointer ('void *') parameters. When you need to pass to a function a "pointer to a user defined record structure", that parameter is declared as a void pointer. This allows you to pass a pointer to anything without generating a compile time warning. However, it is less clear how to declare the address of a "pointer to a user define record structure". If, for example, you are calling a 'find' function, you must pass into that function the address of your pointer so your pointer can be set to the found data record. If this pointer-address parameter is declared as 'void **' you will get a compile time warning when you pass the address of a user defined pointer. If it is declared just as 'void *', the compile warning goes away, but coding could become confusing if you reference the parameter definitions in the function prototype. The compromise I came up with was to document the parameters one way in this manual (as void **), and to declare them the other way in the include file (as void *). FILES AND LIBRARIES INCLUDED The following files are a part of the Salve Data Management Library: READ.ME - Last Minute Instructions SALVE.MAN - Library Manual (this document). SALVE.H - Include File SALVE#.LIB - Optimized Library SALVE#D.LIB - Debug Library EXAMPLE.C - Example Program The # in the library file name is either T for Turbo-C or M for Microsoft-C. All Salve Data Management Functions are compiled in the Large model. There is no reason inherent in the code that prevents them from being compiled in the small or medium model. The Debug library has the same functionality as the Optimized library, with additional code included to provide enhanced error detection and reporting. Critical parameters are tested for validity upon function entry, and standard C run time library functions that are not expected to fail in normal production (such as malloc) are tested after each use. All errors which are detected are, by default, written to the file stdout. The SALVE optimized library follows in the tradition of the standard C runtime library and does very little error checking. The utility function 'set_error_log' can be used to direct the error logging to a different file. - 5 - Copyright Ron Albury 1988 USER SUPPLIED FUNCTIONS KCMPFNC Three classes of data management (list, tree, and hash) require you to provide a KCmpFnc comparison function when opening up a handle. This function is later used when finding elements or adding elements based on a key field. The KCmpFnc function is similar to the C run time library strcmp function. The KCmpFnc function is passed two void pointers. The first parameter points to the data record that has been previously stored by the management routine. The second parameter is a key pointer which has been passed into the 'finding' or 'adding' data management function. The KCmpFnc function must return zero if the key field of the data record is equal to the key parameter, a negative number if the key field of the data record is less than the key parameter, and a positive number if the key parameter is larger. The second (key) parameter of the KCmpFnc function probably will not point to a record format identical to the one stored by the data management class. If you look at the Hadd function you will notice that you must supply it with pointers both to the data record you are adding and to a key field contained in contained that record. This key field pointer is passed as the second that parameter to the KCmpFnc function. I will attempt to explain this in the next paragraph. If you find the explanation confusing just skip it. The Salve routines do not store key fields apart from the rest of the data record. The key field must be contained in the data record. However, there is a definite advantage to having you specify the key field for the KCmpFnc. Refer to the Hfind function. When you are searching for a specific record you do not want to create an empty record structure and populate the key field. You only want to pass in the key. Of course, you could, by design or necessity, provide the basic record pointer as the key field pointer. As long as the KCmpFnc knows if the second parameter is a complete record pointer or just a key field pointer (you couldn't mix and match with a single handle), everything will work fine. HASHFNC The Hash Table class requires you to provide a hash transformation function. This function is passed two parameters. The first parameter is a pointer to the key field of the data record you are putting into the table. The second parameter is the maximum hash value allowable. Typically, the function will transform the key field into a positive integer and then 'mod' that integer by the second parameter. As with KCmpFnc, the key field parameter may or may not point to a record format identical to the one stored by the routine. - 6 - Copyright Ron Albury 1988 BEACHFNC The final user supplied function is only required by the Bfor_each utility. The Bfor_each function requires, as a parameter, a function that takes two parameters and returns void. The first parameter to the user function is an unsigned integer indicating the id of an element which is in a set. The second parameter to the function is a user supplied pointer to what ever you want. The Bfor_each utility calls the user supplied function for each element in the set, and passes in the id of the element and the user supplied pointer. - 7 - Copyright Ron Albury 1988 BIT SET CLASS BIT SET CLASS The C language is generally richer in types and operators than Pascal. One area where Pascal has the upper hand is the 'SET' type. These functions provide most of the set functionality found in Pascal. A set is a collection of objects of the same type. An example of this is the 'character set'. Note that although a set contains multiple items, each item in the set is unique. There are not two upper case A's in the set of characters. A set variable is a single variable used to represent a set containing multiple objects. It is implemented here (as with most Pascal compilers) as a string of bits. Each bit in the set represents one of the objects which could belong to the set. If the bit is turned on it means that the object is in the set. If the bit is turned off it means that the object is not in the set. The objects you add to the set must be an ordinal type (not strings, not floating point, etc.). You can use the set functions to manage sets of characters, sets of integers, or sets of enumerated types. - 8 - Copyright Ron Albury 1988 FUNCTION Badd Badd PURPOSE Adds an element to the indicated set. PARAMETERS Root: (Input) The root of the set being accessed. Bit_Id: (Input) The element to be placed into the set. RETURNS Integer indicating status of the indicated bit before the element was added. 0 = Bit was not set. !0 = Bit was already set. PROTOTYPE int Badd (Broot root, void bit_id); DEBUG The debug library (only) will report: 1) Null root. 2) Bit out of range. EXAMPLE #include "salve.h" main() { Broot root; /* open the bit set */ : : : /* turn on bit 74 */ node = Badd (root, 74); /* use the set */ : : : /* close the set */ } - 9 - Copyright Ron Albury 1988 FUNCTION Bcard Bcard PURPOSE Returns the cardinality (number of elements/number of bits turned on) of the set. PARAMETERS Root: (Input) The root of the set being accessed. RETURNS Long integer indicating number of elements currently in the set. PROTOTYPE long Bcard (Broot root); DEBUG The debug library (only) will report: 1) Null root. EXAMPLE #include "salve.h" main() { Broot root; int quan; /* open the bit set */ : : : /* use the set */ : : : /* find out how many bits are on in the set */ quan = Bcard (root); /* close the set */ } - 10 - Copyright Ron Albury 1988 FUNCTION Bclose Bclose PURPOSE Closes a previously opened bit set. There are NO NO restrictions requiring you to remove all elements before the set is closed. PARAMETERS Root: (Input/Output) The root of the bit set being closed. RETURNS Integer indicating status of the close. 0 = Success. PROTOTYPE int Bclose (Broot *root); DEBUG Both libraries will report: 1) Null root pointer. EXAMPLE #include "salve.h" main() { int status; Broot root; /* open a 200 bit long set */ status = Bopen (&root, 200); : : : /* use the set */ : : : /* close the set */ status = Bclose (&root); } - 11 - Copyright Ron Albury 1988 FUNCTION Bcomplement Bcomplement PURPOSE Creates a second bit set which is the complement (all on bits turned off, all off bits turned on) of the input set. PARAMETERS Orig: (Input) The root of the set being duplicated. Comp: (Output) The new set which is the complement of the input set. RETURNS void. PROTOTYPE void Bcomplement (Broot orig, Broot *comp); DEBUG The debug library (only) will report: 1) Null root. 2) Illegal size for orig. 3) Malloc failure. EXAMPLE #include "salve.h" main() { Broot root, flip; /* open a set */ : : : /* load the set */ : : : /* create a set with all of the bits flipped */ Bcomplement (root, &flip); /* close the sets */ } - 12 - Copyright Ron Albury 1988 FUNCTION Bdifference Bdifference PURPOSE Creates a third bit set which is the difference (bitwise exclusive or) of two input sets. PARAMETERS Root1: (Input) The root of the first set being accessed. Root2: (Input) The root of the second set being accessed. Inter: (Output) The new set which is the difference of the two input sets. RETURNS void. PROTOTYPE void Bdifference (Broot root1, Broot root2, Broot *diff); DEBUG The debug library (only) will report: 1) Null root. 2) Invalid size set. 3) Sets not equal size. 4) Malloc failure - 13 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" void userfunc (unsigned bit, void *ignore) { printf ("bit %u is on\n", bit); } main() { Broot root1, root2, differ; /* open set1 and set2 */ /* load the sets */ : : : /* determine which bits are on in one set but not on in the other */ Bdifference (root1, root2, &differ); /* list all of the bits in the difference set */ Bfor_each (differ, userfunc, NULL); /* close the sets */ } - 14 - Copyright Ron Albury 1988 FUNCTION Bduplicate Bduplicate PURPOSE Creates a second bit set which is the same as the input set. PARAMETERS Orig: (Input) The root of the set being duplicated. Copy: (Output) The new set which is a copy of the input set. RETURNS void. PROTOTYPE void Bduplicate (Broot orig, Broot *copy); DEBUG The debug library (only) will report: 1) Null root. 2) Illegal size set. 3) Malloc failure. EXAMPLE #include "salve.h" main() { Broot root, copy; /* open a set */ : : : /* load the set */ : : : /* duplicate the set */ Bdifference (root, ©); /* close the sets */ } - 15 - Copyright Ron Albury 1988 FUNCTION Bequal Bequal PURPOSE Determines if two bit sets contain the same elements (have the same bits set). PARAMETERS Root1: (Input) The root of the first set being compared. Root2: (Input) The root of the second set being compared. RETURNS An integer indicating the equality of the two sets: < 0 : The first set had a lower bit set. = 0 : The sets are equal. > 0 : The second set had a lower bit set. PROTOTYPE void Bequal (Broot root1, Broot root2); DEBUG The debug library (only) will report: 1) Null root. 2) Illegal size set. 3) Sets not equal size. EXAMPLE #include "salve.h" main() { Broot root1, root2; int status; /* open set1 and set2 */ : : : /* load the sets */ : : : /* determine if the two sets have the same bits turned on */ status = Bequal (root1, root2); /* close the sets */ } - 16 - Copyright Ron Albury 1988 FUNCTION Bfind_next Bfind_next PURPOSE Finds the next element (bit) present (turned on) in the indicated set. To find the first bit set use a 'start' value of zero. PARAMETERS Root: (Input) The root of the set being accessed. Start: (Input) The first bit of the set to be tested. Found: (Output) The first bit encountered in the set which was turned on. If no bits were found this parameter will contain an unpredictable value. RETURNS Integer indicating status of the search. 0 = Bit was found. 1 = No bits were found. PROTOTYPE int Bfind_next (Broot root, unsigned start, unsigned *found); DEBUG The debug library (only) will report: 1) Null root. 2) Illegal size set. 3) Start out of range. - 17 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { Broot root; unsigned bit; int status; /* open the bit set */ /* use the set */ : : : /* find the first 'on' bit in the set */ status = Bfind_next (root, 0, &bit); /* find the next 'on' bit in the set */ status = Bfind_next (root, bit+1, &bit); /* close the set */ } - 18 - Copyright Ron Albury 1988 FUNCTION Bfor_each Bfor_each PURPOSE Performs a user define function for each element (bit) of the set which is present (turned on). PARAMETERS Root: (Input) The root of the set being accessed. Func: (Input) The function to be performed for each element of the set. UserArg: (Input) The address of a user defined parameter to be passed into the function, along with the index of the set bit. RETURNS Integer indicating number of elements currently in the set. PROTOTYPE void Bfor_each (Broot root, BEachFnc func, void *userarg); DEBUG The debug library (only) will report: 1) Null root. 2) Illegal size set. 3) Null BEachFnc. - 19 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" typedef struct { int a; int b; : : } USER; void userfunc (unsigned bit, USER *arg) { /* do something */ } main() { Broot root; USER userarg; /* open the bit set */ : : : /* use the set */ : : : /* call userfunc for each bit in the set */ set_value (&userarg); Bfor_each (root, userfunc, &userarg); /* close the set */ } - 20 - Copyright Ron Albury 1988 FUNCTION Bintersect Bintersect PURPOSE Creates a third bit set which is the intersection (bitwise and) of two input sets. PARAMETERS Root1: (Input) The root of the first set being accessed. Root2: (Input) The root of the second set being accessed. Inter: (Output) The new set which is an intersection of the two input sets. RETURNS void. PROTOTYPE int Bintersect (Broot root1, Broot root2, Broot *inter); DEBUG The debug library (only) will report: 1) Null root. 2) Malloc failure. - 21 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" void userfunc (unsigned bit, void *ignore) { printf ("bit %u is on\n", bit); } main() { Broot root1, root2, inter; /* open set1 and set2 */ /* load the sets */ : : : /* determine which bits are on in both sets */ Bintersect (root1, root2, &inter); /* list all of the bits in the intersection set */ Bfor_each (inter, userfunc, NULL); /* close the sets */ } - 22 - Copyright Ron Albury 1988 FUNCTION Bopen Bopen PURPOSE Opens an unrestricted bit set and creates the data structures necessary for its management. As with Lopen, you must call this function for each bit set to be used. This function is required before any other of the bit set functions can be performed. These routines are comparable to Pascal sets, and are intended for use when sets with more than 32 elements must be managed. For sets with 32 or fewer elements it is more efficient to use bit oriented operations on long or integer variables. PARAMETERS Root: (Output) The root (or handle) of the bit set being opened. Referenced by all other bit set functions. Size: (Input) The number of bits to manage in this set. This number can be as small as two, or as large as can be accommodated by an unsigned value. If you are using the set to manage an enumerated type you may pass in the largest (last) element of the enumerated type for this parameter. RETURNS Integer indicating status of the open. 0 = Success. PROTOTYPE int Bopen (Broot *root, unsigned size); DEBUG Both libraries will report: 1) Null root pointer. 2) Malloc failure. - 23 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" typedef enum { Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday } DAYS_OF_WEEK; main() { int status; Broot root_int, root_days; /* open a 200 bit long set */ status = Bopen (&root_int, 200); : : : /* open a weekday set */ status = Bopen (&root_days, Saturday); : : : } - 24 - Copyright Ron Albury 1988 FUNCTION Bremove Bremove PURPOSE Removes an element from the indicated set. PARAMETERS Root: (Input) The root of the set being accessed. Bit_Id: (Input) The element to remove from the set. RETURNS Integer indicating status of the removal. 0 = Success. PROTOTYPE int Bremove (Broot root, unsigned bit_id); DEBUG The debug library (only) will report: 1) Null root. 2) Invalid bit id. EXAMPLE #include "salve.h" main() { Broot root; /* open the bit set */ : : : /* turn on bit 74 */ node = Badd (root, 74); /* use the set */ : : : /* turn off bit 74 */ node = Bremove (root, 74); /* close the set */ } - 25 - Copyright Ron Albury 1988 FUNCTION Btest_in Btest_in PURPOSE Tests if a specific element (bit) is in the indicated bit set. PARAMETERS Root: (Input) The root of the set being accessed. Bit_Id: (Input) The bit of the set to be tested. RETURNS Integer indicating status of the bit. 0 = Bit is not set. !0 = Bit is set. PROTOTYPE int Btest_in (Broot root, unsigned bit_id); DEBUG The debug library (only) will report: 1) Null root. 2) Invalid bit id. EXAMPLE #include "salve.h" main() { Broot root; int quan; /* open the bit set */ : : : /* use the set */ : : : /* test if bit 48 is in the set */ quan = Btest_in (root, 48); /* close the set */ } - 26 - Copyright Ron Albury 1988 FUNCTION Btoggle Btoggle PURPOSE Toggles an element (xor's it) in the indicated set. PARAMETERS Root: (Input) The root of the set being accessed. Bit_Id: (Input) The element in the set to toggle. RETURNS Integer indicating status of the bit before the toggle. 0 = Bit was not set. !0 = Bit was set. PROTOTYPE int Btoggle (Broot root, void bit_id); DEBUG The debug library (only) will report: 1) Null root. 2) Invalid bit id. EXAMPLE #include "salve.h" main() { Broot root; /* open the bit set */ : : : /* toggle bit 45 */ node = Btoggle (root, 45); /* use the set */ : : : /* close the set */ } - 27 - Copyright Ron Albury 1988 FUNCTION Bunion Bunion PURPOSE Creates a third bit set which is the union (bitwise inclusive or) of two input sets. PARAMETERS Root1: (Input) The root of the first set being accessed. Root2: (Input) The root of the second set being accessed. Union: (Output) The new set which is a union of the two input sets. RETURNS void. PROTOTYPE void Bunion (Broot root1, Broot root2, Broot *union); DEBUG The debug library (only) will report: 1) Null root. 2) Sets not equal size. 3) Malloc failure. - 28 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" void userfunc (unsigned bit, void *ignore) { printf ("bit %u is on\n", bit); } main() { Broot root1, root2, uni; /* open set1 and set2 */ /* load the sets */ : : : /* determine which bits are on in either set */ Bunion (root1, root2, &uni); /* list all of the bits in the union set */ Bfor_each (uni, userfunc, NULL); /* close the sets */ } - 29 - Copyright Ron Albury 1988 HASH TABLE CLASS HASH TABLE CLASS Hashing is the technique of transforming a key value from one format (such as a character string) into another, equivalent format (an integer) that is easier to use as an index. A good transforming function takes the original keys and returns indices which are evenly distributed over a evenly predetermined range. There are a number of factors that determine how evenly the indices are distributed. A good transforming function must take into account the type of data being hashed, and even the choice of the maximum allowable index value. Using a prime number for the maximum value will (for some reason) provide better distribution. Ideally, given unique keys the transformation function will return unique indices. However, we do not live in an ideal world. The hash table functions make provisions for the transform function returning the same index for two unique keys. This collision handling is taken care of by a backup comparison on the original key. A typical approach for transforming character strings is to add up the values of the characters and then mod them by the maximum allowable value. There are algorithms to transform strings based on phonetics, and simpler (and faster transforms) based on just a few selected characters from the character string (e.g the sum of the first character, the last character, and the length of the string). Hashing can be performed on data types other than character strings, but that is the most typical use. Hash tables are frequently used to index other data structures. A typical application would be to have a linked list of records, ordered on a First In First Out or Most Recently Used basis, which has a hash index to allow key based searching. There is, however, no restriction on the use of these hash table functions. They can be use to directly store pointers to large records, or to index other storage techniques. One possible drawback to hash tables is that you can not easily access the data items in the hash table except by direct look-up based on the key. Hash tables generally provide much faster access than sequential search or even binary trees. However, if you need an additional searching technique you must either use a different class of data management to store the data (such as a tree) or combine hashing with another class. - 30 - Copyright Ron Albury 1988 FUNCTION Hadd Hadd PURPOSE Adds a data element to the appropriate slot of the hash table. Duplicate entries are not permitted. PARAMETERS Root: (Input) The root of the table being accessed. Data: (Input) The data element to be placed into the table. Key: (Input) The key field to pass to the compare function for determining table location. This field may be a pointer to a record of the same type as the data element, or it may be a pointer to some other structure (e.g just a field of the data element record structure). RETURNS An Hnode pointer Success: Hash node of the added element. Failure: NULL (duplicate entry found). Hash node of the added element. PROTOTYPE Hnode Hadd (Hroot hroot, void *data, void *key); DEBUG The debug library (only) will report: 1) Null root. 2) Null data. 3) Null key. 4) Malloc failure. - 31 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; char key[32]; Hnode node; Hroot root; /* open the hash table */ : : : /* create a new data element for the table */ u = malloc(sizeof(struct UserRec)); /* assign values to the new data element */ gets (key); assign_values(u, key); /* add the new data to the table */ node = Hadd (root, u, key); /* use the table */ : : : /* close the table */ } - 32 - Copyright Ron Albury 1988 FUNCTION Hcard Hcard PURPOSE Returns the cardinality (number of elements) of the table. PARAMETERS Root: (Input) The root of the table being accessed. RETURNS Long integer indicating number of elements currently in the table. PROTOTYPE long Hcard (Hroot root); DEBUG The debug library (only) will report: 1) Null root. EXAMPLE #include "salve.h" main() { Hroot root; int quan; /* open the hash table */ : : : /* use the table */ : : : /* find out how elements are in the table */ quan = Hcard (root); /* close the table */ } - 33 - Copyright Ron Albury 1988 FUNCTION Hclose Hclose PURPOSE Closes a previously opened hash table. All elements must have been removed from the table before the table is closed. PARAMETERS Root: (Input/Output) The root of the table being closed. RETURNS Integer indicating status of close. 0 = Success. 1 = Elements were left in the table. Remove them and try again. PROTOTYPE int Hclose (Hroot *root); DEBUG Both libraries will report: 1) Null root pointer. EXAMPLE #include "salve.h" main() { int status; Hroot root; /* open the hash table */ : : : /* use the hash table */ : : : status = Hclose (&root); } - 34 - Copyright Ron Albury 1988 FUNCTION Hfind Hfind PURPOSE Finds a data element in the indicated hash table. PARAMETERS Root: (Input) The root of the table being accessed. Key: (Input) The key field to pass to the compare and hash functions for selecting table element. Found: (Output) The data element in the table which matches the key. RETURNS An Hnode pointer Success: Hash node of the found element. Failure: NULL (node not found). PROTOTYPE Hnode Hfind (Hroot root, void *key, void *found); DEBUG The debug library (only) will report: 1) Null root. 2) Null key. 3) Found parameter null. - 35 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; char key[32]; Hnode node; Hroot root; /* open the hash table */ /* add data elements to the table */ : : : /* find the node with a given key */ node = Hfind (root, key, &found); /* use the table */ : : : /* close the table */ } - 36 - Copyright Ron Albury 1988 FUNCTION Hfind_node Hfind_node PURPOSE Finds the data element associated with a hash table node. This function is useful if you store the nodes in another data management structure (such as a tree). PARAMETERS Node: (Input) The hash table node to be used in finding the requested data. Found: (Output) The data element located at that node. RETURNS void. PROTOTYPE void Hfind_node (Hnode node, void **found); DEBUG The debug library (only) will report: 1) Null node. 2) Found parameter null. - 37 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Hnode node; Hroot root; /* open the hash table */ : : : /* add records to the table */ : : : /* cross reference them in a tree */ : : : /* find a node through the tree * : : : /* get the data associated with it */ Hfind_node (node, &u); /* delete the node from the tree and the table */ : : : /* close the table */ } - 38 - Copyright Ron Albury 1988 FUNCTION Hopen Hopen PURPOSE Opens a hash table and creates the data structures necessary for its management. As with Lopen, you must call this function for each hash table to be used. This function is required before any other of the hash functions can be performed on the hash table. Hash tables can be used to index a linked list (in this case the data item stored in the table is the list node) or to store data directly. PARAMETERS Root: (Output) The root (or handle) of the hash table being opened. Referenced by all other hash functions. Quan: (Input) The size of the hash table to create. This should be approximately 1.5 times the estimated quantity of elements to be stored in the table (+ or - 25%. Too few slows down/too many takes up space). Performance may be improved slightly if you choose a prime number for this value. Comp: (Input) The comparison function to be used with this list. This function should return 0 for equal, less than zero if the data is less than the key, and greater than zero if the data is greater than the key. Hash: (Input) The hash function for this table. Given a key value and a modulus, this function should return an integer value in the range of 0 to modulous-1. RETURNS Integer indicating status of the open. 0 = Success. PROTOTYPE int Hopen (Hroot *root, unsigned quan, KCmpFnc comp, HashFnc hash); - 39 - Copyright Ron Albury 1988 DEBUG Both libraries will report: 1) Null root pointer. 2) Invalid quanity. 3) Null compare function. 4) Null hash function. 5) Malloc failure. EXAMPLE #include "salve.h" int compare (void *data, void *key) { /* compare the data with the key */ : : : } int hash (void *key, unsigned mod) { /* calculate a hash value based on the key */ : : : } main() { int status; Hroot root; status = Hopen (&root, 101, compare, hash); : : : } - 40 - Copyright Ron Albury 1988 FUNCTION Hremove Hremove PURPOSE Removes a node and data element from the indicated hash table. PARAMETERS Root: (Input) The root of the table being accessed. Drop_Node: (Input) The hash node of the element to remove. RETURNS Integer indicating status of the removal. 0 = Success. 1 = Corrupted memory, or node not part of table. PROTOTYPE int Hremove (Hroot root, Hnode drop_node); DEBUG The debug library (only) will report: 1) Null root. 2) Null drop node. 3) Node consistency tests. - 41 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; char key[32]; int status; Hnode node; Hroot root; /* open the hash table */ /* add data elements to the table */ : : : /* find the node with a given key */ node = Hfind (root, key, &u); /* remove that node */ status = Hremove (root, node); /* use the table */ : : : /* close the table */ } - 42 - Copyright Ron Albury 1988 FUNCTION Htest Htest PURPOSE Tests a hash node to detect memory corruption or to verify that the element is from the indicated table. PARAMETERS Root: (Input) The root of the table being accessed. Node: (Input) The node of the table to be tested. RETURNS Integer indicating status of test. 0 = Success. 1 = Corrupted memory, or indicated element is not part of this table. PROTOTYPE int Htest (Hroot root, Hnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. - 43 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { int status; struct UserRec *u; Hnode node; Hroot root; /* open the hash table */ : : : /* add records to the table */ : : : /* find the first node with a given key * node = Hfind (root, "Key Field", &u); /* test that node for corruption */ status = Htest (root, node); : : : } - 44 - Copyright Ron Albury 1988 LINKED LIST CLASS LINKED LIST CLASS A linked list is probably the most fundamental dynamic data structure. It allows you to string together multiple items into a list. Unlike a set, you can store non-ordinal values in the list (such as a record), can store duplicates in the list, and can arrange the list in different orders. The ordering of a list can be based on time (First In First F I F Out: Queue; Last In First Out: Stack), on a key value (sorted), O L I F O or on any other basis you can think of (e.g. Most Recently e.g. M R Used). U I generally use lists as my primary method of storing data, and then use the hash table, tree, and/or sparse matrix routines to provide indices into the list. You can use them for what ever you want. One way to code '1 to many' relationships (e.g. one club has many members) is with multiple lists. The first list is the '1' list (such as clubs). Each record of the '1' list contains in it the root for the 'many' list (members). To find all of the members of a specific club you could scan (or index into) the club list, and then scan the sub-list containing all of the members. You can even support 'm to n' relationships (e.g. one club has many members, and one member belongs to many clubs). You have one list of clubs, one list of members, and then a third list of 'belongs to' which is a sub-list to the other two. Although you would (probably) rarely want to scan the 'belongs to' list, it is best to keep the records in a list so that you don't loose them and end up with un-free'd memory lying around. Some people will go so far as to have a master list of all allocated records, no matter what set they belong to. - 45 - Copyright Ron Albury 1988 FUNCTION Ladd_after Ladd_after PURPOSE Adds a new data element to the list after the indicated list node. PARAMETERS Root: (Input) The root of the list being accessed. Data: (Input) The data element to be placed into the list. Node: (Input) The list node of a data element already in the list. This existing node will be used to position the new data element. RETURNS List node of the added element. PROTOTYPE Lnode Ladd_after (Lroot root, void *data, Lnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null data. 3) Null node. 4) Malloc failure. 5) Internal consistency test. - 46 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node1, node2; Lroot root; /* open the list */ : : : /* create a new element for the list */ u = malloc(sizeof(struct UserRec)); assign_values(u); /* add the new record to the head of the list */ node1 = Ladd_first (root, u); /* create another new element for the list */ u = malloc(sizeof(struct UserRec)); assign_values(u); /* add the record second in the list */ node2 = Ladd_after (root, u, node1); /* use the list */ : : : /* close the list */ } - 47 - Copyright Ron Albury 1988 FUNCTION Ladd_before Ladd_before PURPOSE Adds a new data element to the list before the indicated list node. PARAMETERS Root: (Input) The root of the list being accessed. Data: (Input) The data element to be placed into the list. Node: (Input) The list node of a data element already in the list. This existing node will be used to position the new data element. RETURNS List node of the added data element. PROTOTYPE Lnode Ladd_before (Lroot root, void *data, Lnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null data. 3) Null node. 4) Malloc failure. 5) Internal consistency test. - 48 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node1, node2; Lroot root; /* open the list */ : : : /* create a new element for the list */ u = malloc(sizeof(struct UserRec)); assign_values(u); /* add the new record to the end of the list */ node1 = Ladd_last (root, u); /* create another new element for the list */ u = malloc(sizeof(struct UserRec)); assign_values(u); /* add the record next to the end of the list */ node2 = Ladd_before (root, u, node1); /* use the list */ : : : /* close the list */ } - 49 - Copyright Ron Albury 1988 FUNCTION Ladd_first Ladd_first PURPOSE Adds a data element to the head (first position) of the indicated list. PARAMETERS Root: (Input) The root of the list being accessed. Data: (Input) The data element to be placed into the list at the first position. RETURNS List node of the added element. PROTOTYPE Lnode Ladd_first (Lroot root, void *data); DEBUG The debug library (only) will report: 1) Null root. 2) Null data. 3) Malloc failure. - 50 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node; Lroot root; /* open the list */ : : : /* create a new element for the list */ u = malloc(sizeof(struct UserRec)); assign_values(u); /* add the new record to the head of the list */ node = Ladd_first (root, u); /* use the list */ : : : /* close the list */ } - 51 - Copyright Ron Albury 1988 FUNCTION Ladd_last Ladd_last PURPOSE Adds a data element to the tail (last position) of the indicated list. PARAMETERS Root: (Input) The root of the list being accessed. Data: (Input) The data element to be placed at the end of the list. RETURNS List node of the added element. PROTOTYPE Lnode Ladd_last (Lroot root, void *data); DEBUG The debug library (only) will report: 1) Null root. 2) Null data. 3) Malloc failure. - 52 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node; Lroot root; /* open the list */ : : : /* create a new data element for the list */ u = malloc(sizeof(struct UserRec)); /* assign values to the new data element */ assign_values(u); /* add the new data to the tail of the list */ node = Ladd_last (root, u); /* use the list */ : : : /* close the list */ } - 53 - Copyright Ron Albury 1988 FUNCTION Ladd_order Ladd_order PURPOSE Adds a data element to the indicated list in sorted order. This function ASSUMES that ALL elements in the list have been ALL added IN ORDER, and that the order has not been corrupted by other calls (e.g. you may NOT use Lmake_first, Ladd_last, NOT etc.). Violate this assumption at your own risk. PARAMETERS Root: (Input) The root of the list being accessed. Data: (Input) The data element to be placed into the list. Key: (Input) The key field to pass to the compare function for determining order. This field may be a pointer to a record of the same type as the data element, or it may be a pointer to some other structure (e.g just a field of the data element record structure). Dupe: (Input) OK_DUPE means duplicates are permitted, NO_DUPE means duplicates indicate an error condition. RETURNS An Lnode pointer Success: List node of the added element. Failure: NULL (duplicate entry found). PROTOTYPE Lnode Ladd_order (Lroot root, void *data, void *key, int dupe); DEBUG The debug library (only) will report: 1) Null root. 2) Null data. 3) Null key. 4) Internal consistency test. - 54 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; char key[20]; Lnode node; Lroot root; /* open the list */ : : : /* create a new data element for the list */ u = malloc(sizeof(struct UserRec)); /* assign values to the data element */ gets (key); assign_values(u, key); /* add the new record to the list */ node = Ladd_order (root, u, key, NO_DUPE); /* use the list */ : : : /* close the list */ } - 55 - Copyright Ron Albury 1988 FUNCTION Lcard Lcard PURPOSE Returns the cardinality (number of elements) of the list. PARAMETERS Root: (Input) The root of the list being accessed. RETURNS Long integer indicating number of elements currently in the list. PROTOTYPE long Lcard (Lroot root); DEBUG The debug library (only) will report: 1) Null root. EXAMPLE #include "salve.h" main() { Lroot root; long quan; /* open the list */ : : : /* use the list */ : : : /* find out how elements are in the list */ quan = Lcard (root); /* close the list */ } - 56 - Copyright Ron Albury 1988 FUNCTION Lclose Lclose PURPOSE Closes a previously opened linked list. All nodes and data elements must have been removed from the list before the list is closed. PARAMETERS Root: (Input/Output) The root of the list being closed. This must be the root parameter which was returned from the Lopen function when the list was opened. RETURNS An integer indicating the status of the call. 0 = Success. 1 = Elements were left in the list. Remove them and try again. PROTOTYPE int Lclose (Lroot *root); DEBUG Both libraries will report: 1) Null root. 2) Internal consistency test. EXAMPLE #include "salve.h" main() { int status; Lroot root; /* open the list */ : : : /* use the list */ : : : status = Lclose (&root); } - 57 - Copyright Ron Albury 1988 FUNCTION Lfind Lfind PURPOSE Does a sequential search of a list to find a data element with a specified key field. The list does not need to be inorder for this function to work. PARAMETERS Root: (Input) The root of the list being accessed. Key: (Input) The key field to be used in finding the requested element. Found: (Output) The first element in the list with a matching key. Flag: (Input) Either FIND_EQ (if there must be an exact match) or FIND_GE (if you are willing to stop searching at the first element with a key greater or equal to the search key). For performance reasons it is suggested that you always use FIND_GE when searching an ordered always list. RETURNS An Lnode pointer Success: List node of the found element. Failure: NULL (node not found). PROTOTYPE Lnode Lfind (Lroot root, void *key, void **found, int flag); DEBUG The debug library (only) will report: 1) Null root. 2) Null key. 3) Null found. 4) Internal consistency test. - 58 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node; Lroot root; /* open the list */ /* add records to the list - NOT in order */ : : : /* find the first node with a given key * node = Lfind (root, "Key Field", &u, FIND_EQ); /* close the list */ } - 59 - Copyright Ron Albury 1988 FUNCTION Lfind_after Lfind_after PURPOSE Finds the data element in the list after the indicated list node. PARAMETERS Root: (Input) The root of the list being accessed. Node: (Input) The list node to be used in finding the requested element. Found: (Output) The next element in the list. RETURNS An Lnode pointer Success: List node of the found element. Failure: NULL (node not found). PROTOTYPE Lnode Lfind_after (Lroot root, Lnode node, void **found); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. 3) Null found. - 60 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node1, node2; Lroot root; /* open the list */ : : : /* add records to the list */ : : : /* find the first element in the list * node1 = Lfind_first (root, &u); /* find the second element in the list * node2 = Lfind_after (root, node1, &u); /* close the list */ } - 61 - Copyright Ron Albury 1988 FUNCTION Lfind_before Lfind_before PURPOSE Finds the data element in the list before the indicated list node. PARAMETERS Root: (Input) The root of the list being accessed. Node: (Input) The list node to be used in finding the requested data element. Found: (Output) The prior element in the list. RETURNS An Lnode pointer Success: List node of the found element. Failure: NULL (node not found). PROTOTYPE Lnode Lfind_before (Lroot root, Lnode node, void **found); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. 3) Null found. - 62 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node1, node2; Lroot root; /* open the list */ : : : /* add records to the list */ : : : /* find the last element in the list * node1 = Lfind_last (root, &u); /* find the next to the last element in the list * node2 = Lfind_before (root, node1, &u); /* close the list */ } - 63 - Copyright Ron Albury 1988 FUNCTION Lfind_first Lfind_first PURPOSE Finds the first data element stored in the indicated list. PARAMETERS Root: (Input) The root of the list being accessed. Found: (Output) The first data element in the list. RETURNS An Lnode pointer Success: List node of the found element. Failure: NULL (node not found). PROTOTYPE Lnode Lfind_first (Lroot root, void **found); DEBUG The debug library (only) will report: 1) Null root. 2) Null found. EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node; Lroot root; /* open the list */ : : : /* add records to the list */ : : : /* find the first element in the list */ node = Lfind_first (root, &u); /* use the list */ : : : /* close the list */ } - 64 - Copyright Ron Albury 1988 FUNCTION Lfind_last Lfind_last PURPOSE Finds the last data element of the indicated list. PARAMETERS Root: (Input) The root of the list being accessed. Found: (Output) The last data element in the list. RETURNS An Lnode pointer Success: List node of the found element. Failure: NULL (node not found). PROTOTYPE Lnode Lfind_last (Lroot root, void **found_data); DEBUG The debug library (only) will report: 1) Null root. 2) Null found. EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node; Lroot root; /* open the list */ : : : /* add records to the list */ : : : /* find the last element in the list */ node = Lfind_last (root, &u); /* use the list */ : : : /* close the list */ } - 65 - Copyright Ron Albury 1988 FUNCTION Lfind_next Lfind_next PURPOSE Finds next data element in the list with the indicated key field. This function is primarily used with unsorted lists with non-unique entries. PARAMETERS Root: (Input) The root of the list being accessed. Node: (Input) The list node to be used as the starting point in the search for the requested element. Key: (Input) The key field to be used in finding the requested data element. Found: (Output) The next element in the list with a matching key. RETURNS An Lnode pointer Success: List node of the found element. Failure: NULL (node not found). PROTOTYPE Lnode Lfind_next (Lroot root, Lnode node, void *key, void **found); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. 3) Null key. 4) Null found. 5) Internal consistency test. - 66 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node1, node2; Lroot root; /* open the list */ : : : /* add records to the list */ : : : /* find the first node with a given key * node1 = Lfind (root, "Key Field", &u, FIND_EQ); /* find the next node with the same key * node2 = Lfind_next (root, node1, "Key Field", &u); /* close the list */ } - 67 - Copyright Ron Albury 1988 FUNCTION Lfind_node Lfind_node PURPOSE Finds the data element associated with a list node. This function is useful if you store the list nodes in another data management structure (such as a hash table). PARAMETERS Node: (Input) The list node to be used in finding the requested data. Found: (Output) The data element located at that node. RETURNS void. PROTOTYPE void Lfind_node (Lnode node, void **found); DEBUG The debug library (only) will report: 1) Null node. 2) Null found. - 68 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node; Lroot root; /* open the list */ : : : /* add records to the list */ : : : /* cross reference them in a hash table */ : : : /* find a node through the hash table * : : : /* get the data associated with it */ Lfind_node (node, &u); /* delete the node from the list and the table */ : : : /* close the list */ } - 69 - Copyright Ron Albury 1988 FUNCTION Lmake_first Lmake_first PURPOSE Moves a data element from its current position in the list to the first position. This function is more efficient than deleting a node from the middle of the list and adding it at the head of the list. PARAMETERS Root: (Input) The root of the list being accessed. Node: (Output) The list node of the element to be moved. RETURNS Integer indicating status of the move. 0 = Success. 1 = Corrupted memory, or indicated element is not part of this list. PROTOTYPE int Lmake_first (Lroot root, Lnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. 3) Internal consistency test. - 70 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Lnode node; Lroot root; /* open the list */ : : : /* add records to the list */ : : : /* find the first node with a given key * node = Lfind (root, "Key Field", &u, FIND_EQ); /* make this (the most recently used node) first * Lmake_first (root, node); /* close the list */ } - 71 - Copyright Ron Albury 1988 FUNCTION Lopen Lopen PURPOSE Opens a linked list and creates the data structures necessary for it's management. As with a file, each list must be opened before it can be used in your program. This function is required before any other of the list operations can be performed on the list. If you plan to perform searches on the list based on a key field you must associate a key comparison function with the list when it is opened. PARAMETERS Root: (Output) The root (or handle) of the list being opened. This parameter is referenced by all other list functions. Comp: (Input) The comparison function to be used with this list (may be NULL if you are not ordering you list by key values). See the introduction for a description of this function and Lfind for an application of this function. RETURNS An integer indicating the status of the call. 0 = Success. PROTOTYPE int Lopen (Lroot *root, KCmpFnc comp); DEBUG Both libraries will report: 1) Null root pointer. 2) Malloc failure. - 72 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" int compare (void *data, void *key) { /* compare the data with the key */ } main() { int status; Lroot root; status = Lopen (&root, compare); : : : } - 73 - Copyright Ron Albury 1988 FUNCTION Lremove Lremove PURPOSE Removes a node and data element from the indicated list. PARAMETERS Root: (Input) The root of the list being accessed. Node: (Output) The list node of the element to be removed. RETURNS Integer indicating status of removal. 0 = Success. 1 = Corrupted memory, or indicated element is not part of this list. PROTOTYPE int Lremove (Lroot root, Lnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. 3) Internal consistency test. - 74 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { int status; struct UserRec *u; Lnode node; Lroot root; /* open the list */ /* add records to the list */ : : : /* find the first node with a given key * node = Lfind (root, "Key Field", &u); /* remove that node */ status = Lremove (root, node); : : : } - 75 - Copyright Ron Albury 1988 FUNCTION Ltest Ltest PURPOSE Tests a list node to detect memory corruption and to verify that the node is from the indicated list. PARAMETERS Root: (Input) The root of the list being accessed. Node: (Output) The node to be tested. RETURNS Integer indicating status of test. 0 = Success. 1 = Corrupted memory, or indicated element is not part of this list. PROTOTYPE int Ltest (Lroot root, Lnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. - 76 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { int status; struct UserRec *u; Lnode node; Lroot root; /* open the list */ /* add records to the list */ : : : /* find the first node with a given key * node = Lfind (root, "Key Field", &u); /* test that node for corruption */ status = Ltest (root, node); : : : } - 77 - Copyright Ron Albury 1988 SPARSE MATRIX CLASS SPARSE MATRIX CLASS Probably the easiest analogy for a sparse matrix is a spread sheet. You have lots of potential places to put data, but you only use a few of them. Rather than allocate a huge array of record structures (or even a slightly less huge array of pointers to record structures) you may want to use these routines. The following functions allow you to have as many dimensions in the array as you want. It's only limitation is that you have some idea of how many elements will eventually end up in the matrix. A matrix is a good tool whenever you have lots of data you need to access based on multiple numeric keys. You could, for instance, use height, weight, and age for the three dimensions of the matrix, and have the entry be a list of all children that fall into that category. This would be accomplished by storing in the matrix the root of a list. There are many other ways to implement a sparse matrix, some of which may be faster for your application. These functions are included to provide a full set of capability within the Salve Data Management functions, and to provide a common interface for you should you need a sparse matrix. - 78 - Copyright Ron Albury 1988 FUNCTION Madd Madd PURPOSE Adds an element to the appropriate cell of the matrix. PARAMETERS Root: (Input) The root of the matrix being accessed. Data: (Input) The element to be placed into the matrix. Indx: (Input) The index of the matrix to place this element. This is a list of integers (one for each dimension) indicating row, column, etc. RETURNS Matrix node of the added element. PROTOTYPE Mnode Madd (Mroot root, void *data, ...); DEBUG The debug library (only) will report: 1) Null root. 2) Null data. 3) Malloc failure. - 79 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; char key[32]; Mnode node; Mroot root; /* open the matrix */ : : : /* create a new data element for the matrix */ u = malloc(sizeof(struct UserRec)); /* assign values to the new data element */ gets (key); assign_values(u, key); /* add the new data to the matrix */ node = Madd (root, u, 3, 5, 2, 1); /* use the matrix */ : : : /* close the matrix */ } - 80 - Copyright Ron Albury 1988 FUNCTION Mcard Mcard PURPOSE Returns the cardinality (number of elements) of the matrix. PARAMETERS Root: (Input) The root of the matrix being accessed. RETURNS Long integer indicating number of elements currently in the matrix. PROTOTYPE long Mcard (Mroot root); DEBUG The debug library (only) will report: 1) Null root. EXAMPLE #include "salve.h" main() { Mroot root; long quan; /* open the matrix */ : : : /* use the matrix */ : : : /* find out how elements are in the matrix */ quan = Mcard (root); /* close the matrix */ } - 81 - Copyright Ron Albury 1988 FUNCTION Mclose Mclose PURPOSE Closes a previously opened matrix. All elements must have been removed from the matrix before the matrix is closed. PARAMETERS Root: (Input/Output) The root of the matrix being closed. RETURNS Integer indicating status of the close. 0 = Success. 1 = Elements were left in the matrix. Remove them and try again. PROTOTYPE int Mclose (Mroot *root); DEBUG The debug library (only) will report: 1) Null root pointer. EXAMPLE #include "salve.h" main() { int status; Mroot root; /* open the matrix */ /* use the matrix */ : : : status = Mclose (&root); } - 82 - Copyright Ron Albury 1988 FUNCTION Mfind Mfind PURPOSE Finds an element in the indicated matrix. PARAMETERS Root: (Input) The root of the matrix being accessed. Found: (Output) The element in the matrix which is at the indicated location. Indx: (Input) The index of the matrix to locate this element. This is a list of integers (one for each dimension) indicating row, column, etc. RETURNS A Mnode pointer Success: Matrix node of the found element. Failure: NULL (no element at that index) PROTOTYPE Mnode Mfind (Mroot root, void **found, ...); DEBUG The debug library (only) will report: 1) Null root. 2) Null found. 3) Malloc failure. 4) Internal consistency check. - 83 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Mnode node; Mroot root; /* open the matrix */ /* add records to the matrix */ : : : /* find a node in the matrix * gets (key) node = Mfind (root, &u, 6, 4, 18, 49); /* use the matrix */ : : : /* close the matrix */ } - 84 - Copyright Ron Albury 1988 FUNCTION Mfind_node Mfind_node PURPOSE Finds the data element associated with a matrix node. This function is useful if you store the matrix nodes in another data management structure (such as a hash table). PARAMETERS Node: (Input) The matrix node to be used in finding the requested data. Found: (Output) The data element located at that node. RETURNS void. PROTOTYPE void Mfind_node (Mnode node, void **found); DEBUG The debug library (only) will report: 1) Null node. 2) Null found. - 85 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Mnode node; Mroot root; /* open the matrix */ /* add records to the matrix */ /* cross reference them in a hash table */ : : : /* find a node through the hash table * : : : /* get the data associated with it */ Mfind_node (node, &u); /* delete the node from the matrix and the table */ : : : /* close the matrix */ } - 86 - Copyright Ron Albury 1988 FUNCTION Mopen Mopen PURPOSE Opens a sparse matrix and creates the data structures necessary for its management. As with Lopen, you must call this function for each matrix to be used. This function is required before any other of the matrix functions can be performed. A matrix can be used to index a linked list (the data item stored in the matrix is the link node) or to store data directly. Any matrix of known size with more than 1/2 of the cells filled should consider using a multi dimensional array of records (or of pointers to records) instead of these sparse matrix routines. PARAMETERS Root: (Output) The root (or handle) of the matrix being opened. Referenced by all other matrix functions. Dim: (Input) The number of dimensions to use for this matrix. Quan: (Input) Estimated number of elements to be stored in the matrix (+ or - 25% - too few slows down/too many takes up space). RETURNS Integer indicating status of the open. 0 = Success. PROTOTYPE int Mopen (Mroot *root, unsigned dim, unsigned quan); DEBUG Both libraries will report: 1) Null root pointer. 2) Too few dimensions. 3) Small quantity. 4) Malloc failure. - 87 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { int status; Mroot root; /* open a four dimensional sparse matrix to hold approximately 100 elements */ status = Mopen (&root, 4, 100); : : : } - 88 - Copyright Ron Albury 1988 FUNCTION Mremove Mremove PURPOSE Removes a node and data element from the indicated matrix. PARAMETERS Root: (Input) The root of the matrix being accessed. Node: (Input) The matrix node of the element to remove. RETURNS Integer indicating status of the removal. 0 = Success. 1 = Corrupted memory, or indicated element is not part of this matrix. PROTOTYPE int Mremove (Mroot root, Mnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. - 89 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Mnode node; Mroot root; /* open the matrix */ /* add records to the matrix */ : : : /* find a node in the matrix * gets (key) node = Mfind (root, &u, 55, 32, 47); /* delete that node */ Mremove (root, node) /* use the matrix */ : : : /* close the matrix */ } - 90 - Copyright Ron Albury 1988 FUNCTION Mtest Mtest PURPOSE Tests a matrix node to detect memory corruption or to verify that the element is from the indicated matrix. PARAMETERS Root: (Input) The root of the matrix being accessed. Node: (Input) The matrix node to be tested. RETURNS Integer indicating status of the test. 0 = Success. 1 = Corrupted memory, or indicated element is not part of this matrix. PROTOTYPE int Mtest (Mroot root, Mnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. - 91 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { int status; struct UserRec *u; Mnode node; Mroot root; /* open the matrix */ /* add records to the matrix */ : : : /* find a node in the matrix */ node = Mfind_first (root, &u, 88, 74, 32); /* test that node for corruption */ status = Mtest (root, node); : : : } - 92 - Copyright Ron Albury 1988 BINARY TREE CLASS BINARY TREE CLASS Binary trees are probably the most common tool to store keyed data, especially if you need to access the data based on the order of the keys. They provide fast access (relative to a sequential search), and can grow to any size. However, they are not as fast as hashing, and can searching can degrade to worse than sequential search speed if the elements are added to the tree in order. Trees work best if the records are entered in random order. It is possible to perform transforms on the tree while you are entering data to 'balance' a tree. This will avoid the degradation from in-order entry. However, balancing a tree can take quite a bit of work It is usually inappropriate unless you plan to build a tree and then leave it static except for look-ups. Also, a balanced tree does not always provide the best look-up performance. Ideally, the most frequently accesses nodes of the tree would be closest to the top. In the case of a 'static' tree you are better off loading the tree based on frequency of use than having a behind-the-scenes algorithm balance the tree for you. The routines provided here are just plain old binary trees. There is no balancing, and there is no adjustment of the tree based on frequency of use. - 93 - Copyright Ron Albury 1988 FUNCTION Tadd Tadd PURPOSE Adds a data element to the appropriate branch of the tree. Duplicate entries are not permitted. PARAMETERS Root: (Input) The root of the tree being accessed. Data: (Input) The data element to be placed into the tree. Key: (Input) The key field to pass to the compare function for determining the location in the tree for the data element. This field may be a pointer to the data element, a pointer to a record of the same type as the data element, or it may be a pointer to some other structure (e.g just a field of the data element record structure). RETURNS A Tnode pointer Success: Tree node of the added element. Failure: NULL (duplicate entry found). PROTOTYPE Tnode Tadd (Troot troot, void *data, void *key); DEBUG The debug library (only) will report: 1) Null root. 2) Null data. 3) Null key. 4) Malloc failure. - 94 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; char key[32]; Tnode node; Troot root; /* open the tree */ : : : /* create a new data element for the tree */ u = malloc(sizeof(struct UserRec)); /* assign values to the new data element */ gets (key); assign_values(u, key); /* add the new data to the tree */ node = Tadd (root, u, key); /* use the tree */ : : : /* close the tree */ } - 95 - Copyright Ron Albury 1988 FUNCTION Tcard Tcard PURPOSE Returns the cardinality (number of elements) of the tree. PARAMETERS Root: (Input) The root of the tree being accessed. RETURNS Long integer indicating number of elements currently in the tree. PROTOTYPE long Tcard (Troot root); DEBUG The debug library (only) will report: 1) Null root. EXAMPLE #include "salve.h" main() { Troot root; long quan; /* open the tree */ : : : /* use the tree */ : : : /* find out how elements are in the tree */ quan = Tcard (root); /* close the tree */ } - 96 - Copyright Ron Albury 1988 FUNCTION Tclose Tclose PURPOSE Closes a previously opened tree. All nodes and data elements must have been removed from the tree before the tree is closed. PARAMETERS Root: (Input/Output) The root of the tree being closed. RETURNS Integer indicating status of close. 0 = Success. 1 = Elements were left in the tree. Remove them and try again. PROTOTYPE int Tclose (Troot *root); DEBUG Both libraries will report: 1) Null root. 2) Internal consistency test. EXAMPLE #include "salve.h" main() { int status; Troot root; /* open the tree */ /* use the tree */ : : : status = Tclose (&root); } - 97 - Copyright Ron Albury 1988 FUNCTION Tfind Tfind PURPOSE Finds an element in the indicated tree. PARAMETERS Root: (Input) The root of the tree being accessed. Key: (Input) The key field which is passed to the compare function for selecting the tree element. Found: (Output) The element in the tree which matches the key. RETURNS A Tnode pointer Success: Tree node of the found element. Failure: NULL (entry not found) PROTOTYPE Tnode Tfind (Troot troot, void *key, void **found); DEBUG The debug library (only) will report: 1) Null root. 2) Null key. 3) Null found. - 98 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Tnode node; Troot root; /* open the tree */ /* add records to the tree */ : : : /* find a node in the tree * gets (key) node = Tfind (root, key, &u); /* use the tree */ : : : /* close the tree */ } - 99 - Copyright Ron Albury 1988 FUNCTION Tfind_first Tfind_first PURPOSE Finds the smallest element (based on the supplied compare function) in the indicated tree. PARAMETERS Root: (Input) The root of the tree being accessed. Found: (Output) The smallest data element in the tree. RETURNS A Tnode pointer Success: Tree node of the found element. Failure: NULL (empty tree) PROTOTYPE Tnode Tfind_first (Troot troot, void **found); DEBUG The debug library (only) will report: 1) Null root. 2) Null found. EXAMPLE #include "salve.h" main() { struct UserRec *u; Tnode node; Troot root; /* open the tree */ /* add records to the tree */ : : : /* find the first node in the tree * node = Tfind_first (root, &u); /* use the tree */ : : : /* close the tree */ } - 100 - Copyright Ron Albury 1988 FUNCTION Tfind_next Tfind_next PURPOSE Finds the next data element in the indicated tree. PARAMETERS Root: (Input) The root of the tree being accessed. Node: The tree node prior to the requested element. Found: (Output) The data element in the tree following the indicated node.. RETURNS A Tnode pointer Success: Tree node of the found element. Failure: NULL (indicated node was the last node in the tree). PROTOTYPE Tnode Tfind_next (Troot troot, Tnode prior, void **found); DEBUG The debug library (only) will report: 1) Null root. 2) Null prior. 3) Null found. - 101 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Tnode node; Troot root; /* open the tree */ : : : /* add records to the tree */ : : : /* find the first node in the tree */ node = Tfind_first (root, &u); /* traverse the rest of the tree in order */ while (node != NULL) { /* use the node */ : : : /* get the next node */ node = Tfind_next (root, node, &u); } /* use the tree */ : : : /* close the tree */ } - 102 - Copyright Ron Albury 1988 FUNCTION Tfind_node Tfind_node PURPOSE Finds the data element associated with a tree node. This function is useful if you store the tree nodes in another data management structure (such as a hash table). PARAMETERS Node: (Input) The tree node to be used in finding the requested data. Found: (Output) The data element located at that node. RETURNS void. PROTOTYPE void Tfind_node (Tnode node, void **found); DEBUG The debug library (only) will report: 1) Null node. 2) Null found. - 103 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Tnode node; Troot root; /* open the tree */ /* add records to the tree */ /* cross reference them in a hash table */ /* find a node through the hash table * : : : /* get the data associated with it */ Tfind_node (node, &u); /* delete the node from the tree and the table */ : : : /* close the tree */ } - 104 - Copyright Ron Albury 1988 FUNCTION Topen Topen PURPOSE Opens a binary tree and creates the data structures necessary for its management. As with a list, each tree must be opened before it can be used in your program. This function is required before any other of the tree functions can be performed. Trees can be used to index a linked list (the data item stored in the tree is the link node) or to store data directly. PARAMETERS Root: (Output) The root or handle of the tree being opened. This parameter is referenced by all other tree functions. Comp: (Input) The comparison function to be used with this tree. This function should return zero for equal, less than zero if the data is less than the key, and greater than zero if the data is greater than the key. RETURNS Integer indicating status of open. 0 = Success. PROTOTYPE int Topen (Troot *root, KCmpFnc comp); DEBUG Both libraries will report: 1) Null root pointer. 2) Null comparison function. 3) Malloc failure. - 105 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" int compare (void *data, void *key) { /* compare the data with the key */ } main() { int status; Troot root; status = Topen (&root, compare); : : : } - 106 - Copyright Ron Albury 1988 FUNCTION Tremove Tremove PURPOSE Removes a node and data element from the indicated tree. PARAMETERS Root: (Input) The root of the tree being accessed. Node: (Input) The tree node of the element to remove. RETURNS Integer indicating status of the removal. 0 = Success. 1 = Corrupted memory, or indicated element is not part of this tree. PROTOTYPE void Tremove (Troot root, Tnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null drop node. - 107 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { struct UserRec *u; Tnode node; Troot root; /* open the tree */ /* add records to the tree */ : : : /* find a node in the tree * gets (key) node = Tfind (root, key, &u); /* delete that node */ Tremove (root, node) /* use the tree */ : : : /* close the tree */ } - 108 - Copyright Ron Albury 1988 FUNCTION Ttest Ttest PURPOSE Tests a tree node to detect memory corruption or to verify that the element is from the indicated tree. PARAMETERS Root: The root of the tree being accessed. Node: The node of the tree to be tested. RETURNS Integer indicating status of test. 0 = Success. 1 = Corrupted memory, or indicated element is not part of this tree. PROTOTYPE int Ttest (Troot troot, Tnode node); DEBUG The debug library (only) will report: 1) Null root. 2) Null node. - 109 - Copyright Ron Albury 1988 EXAMPLE #include "salve.h" main() { int status; struct UserRec *u; Tnode node; Troot root; /* open the tree */ : : : /* add records to the tree */ : : : /* find the first node in the tree */ node = Tfind_first (root, &u); /* test that node for corruption */ status = Ttest (root, node); : : : } - 110 - Copyright Ron Albury 1988 UTILITIES UTILITIES There are plans to provide a number of utility programs to assist in the design and development of application using the Salve Data Management Functions. However, at this time there is only one function and one program which are ready for release. - 111 - Copyright Ron Albury 1988 FUNCTION ERROR_REPORT ERROR_REPORT PURPOSE This is the general error logging utility used in the SALVE debug library. Whenever a 'debug' error is detected, this function is called. This function performs I/O to file stderr. This output can be re-directed using the function SET_ERROR_LOG. You can also replace this function with another one of your own design. PARAMETERS Filename: The name of the file the error was detected in. Line: The line of the file where the error occurred. Format: The format to use with fprintf when displaying the error. This format may (or may not) include a %d to display the (optional) error code parameter. Errcode: An optional integer error code. RETURNS void. PROTOTYPE void error_report (char *filename, int line, char *format, int errcode); EXAMPLE #include "salve.h" main() { int status; /* do something */ status = something(); /* report possible error */ if (status) error_report (__FILE__, __LINE__, "Error doing something = %d\n", status); : : : } - 112 - Copyright Ron Albury 1988 FUNCTION SET_ERROR_LOG SET_ERROR_LOG PURPOSE Redirects debugging output. PARAMETERS Filename: The name of the file to use for debug logging. RETURNS Integer indicating status of test. 0 = Success. !0 = Unable to open file. PROTOTYPE int set_error_log (char *filename); EXAMPLE #include "salve.h" main() { int status; /* direct error logging to file err.log */ status = set_error_log ("err.log"); : : : } - 113 - Copyright Ron Albury 1988 PROGRAM LLDEF LLDEF PURPOSE The LLDEF program will automatically generate custom include files for your programs. These include files will allow you to perform strong type checking for the different data types being controlled through the Salve Data Management Routines. LLDEF will create an include file with an alias and an appropriate function prototype for the each of the specified data management routines. Use of this file allows the compiler to more easily detect errors in your source code. COMMAND LINE PARAMETERS LLDEF can be invoked with 1-n argument pairs. Each argument pair consists of: Function Set: One or more of the letters LHTMB, indicating if aliases should be generated for the List, Hash, Tree, L H T Matrix and/or Bit set routines (e.g LH or LMT). M B Record Types: A list of one or more pointer typedef's for which to generate the aliases. It is best to use short names here. EXAMPLE If you were managing lists of the following data structure: typedef struct { int a; int b; : : } Pxrec, *Px; and wanted to manage them in a list you would invoke the program with the following command line: LLDEF L Px > PX.H This tells the program that you want PX aliases and function declarations for each of the list management routines. The Ladd_first function is aliased as PxLadd_first, the Ladd_order function is aliased as PxLadd_order, etc.. The void *data parameters for the aliased functions are changed to Px *data parameters. Once you have corrected any compilation errors the prototypes detect, a simple change of a compile time constant 'un-aliases' the functions and allows the linker to find them in the library. - 114 - Copyright Ron Albury 1988 The generated declarations are written to standard output, and must be re-directed to disk file for inclusion in your programs. - 115 - INTRODUCTION 1 SALVE SOFTWARE 1 SHAREWARE 1 DESIGN APPROACH 2 USE OF POINTERS IN FUNCTIONS 5 FILES AND LIBRARIES INCLUDED 5 USER SUPPLIED FUNCTIONS 6 BIT SET CLASS 8 FUNCTION Badd 9 FUNCTION Bcard 10 FUNCTION Bclose 11 FUNCTION Bcomplement 12 FUNCTION Bdifference 13 FUNCTION Bduplicate 15 FUNCTION Bequal 16 FUNCTION Bfind_next 17 FUNCTION Bfor_each 19 FUNCTION Bintersect 21 FUNCTION Bopen 23 FUNCTION Bremove 25 FUNCTION Btest_in 26 FUNCTION Btoggle 27 FUNCTION Bunion 28 HASH TABLE CLASS 30 FUNCTION Hadd 31 FUNCTION Hcard 33 FUNCTION Hclose 34 FUNCTION Hfind 35 FUNCTION Hfind_node 37 FUNCTION Hopen 39 FUNCTION Hremove 41 FUNCTION Htest 43 LINKED LIST CLASS 45 FUNCTION Ladd_after 46 FUNCTION Ladd_before 48 FUNCTION Ladd_first 50 FUNCTION Ladd_last 52 FUNCTION Ladd_order 54 FUNCTION Lcard 56 FUNCTION Lclose 57 FUNCTION Lfind 58 FUNCTION Lfind_after 60 FUNCTION Lfind_before 62 FUNCTION Lfind_first 64 FUNCTION Lfind_last 65 FUNCTION Lfind_next 66 FUNCTION Lfind_node 68 FUNCTION Lmake_first 70 FUNCTION Lopen 72 FUNCTION Lremove 74 FUNCTION Ltest 76 SPARSE MATRIX CLASS 78 FUNCTION Madd 79 FUNCTION Mcard 81 FUNCTION Mclose 82 FUNCTION Mfind 83 FUNCTION Mfind_node 85 FUNCTION Mopen 87 FUNCTION Mremove 89 FUNCTION Mtest 91 BINARY TREE CLASS 93 FUNCTION Tadd 94 FUNCTION Tcard 96 FUNCTION Tclose 97 FUNCTION Tfind 98 FUNCTION Tfind_first 100 FUNCTION Tfind_next 101 FUNCTION Tfind_node 103 FUNCTION Topen 105 FUNCTION Tremove 107 FUNCTION Ttest 109 UTILITIES 111 FUNCTION error_report 112 FUNCTION set_error_log 113 PROGRAM LLDEF 114